perm filename V2M.IN[1,DEK] blob
sn#285520 filedate 1977-05-29 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00010 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 folio 595 galley 1 NOTE: The next nine galleys were all pretty much lost.
C00021 00003 folio 595 galley 2
C00035 00004 folio 598 galley 3
C00036 00005 folio 600 galley 4
C00041 00006 folio 604 galley 5
C00044 00007 folio 609 galley 6
C00052 00008 folio 611 galley 7
C00068 00009 folio 614 galley 8
C00071 00010 folio 618 galley 9
C00077 ENDMK
C⊗;
folio 595 galley 1 NOTE: The next nine galleys were all pretty much lost.
0 {U0}{H10L12M29}|πW58320#Computer|9Programming!ch.
1 4!f. 592!g. 1|'{A6}|εProof.|9|4|πWe may assume
7 that |εt|4|¬Q|42, |πsince the result of the theorem
15 is true without restriction on the |εe'|πs when
23 |εt|4|¬R|42. |πSuppose that we have a star chain
31 1|4α=↓|4|εa|β0|4|¬W|4a|β1|4|¬W|4|¬O|4|¬O|4|¬O|4|¬W|4a|βr|4α=
31 ↓|4n |πfor |εn |πwith |εr|4|¬E|4e|β0|4α+↓|4t|4α_↓|41.
36 |πLet the integers |εd, f, d|β0,|4.|4.|4.|4,|4d|βr,
42 |πand the multisets |εM|βi|βj |πand |ε*3|βi |πrd&&ct
49 thesstrkkourdsof this chain, as de_ned earlier.
55 By the corollary to ThebrexnA≡,qaskfm∧qhhuw |\*2F44¬}S44[∩377
60 77)H4↓↓45([∩\;|[πhyjjfxgjshhys Q*2m [7cnn7)iusiunbmkui≠dsiqpp
62 drnboknd eakh mulliset |\(|βj*2[]][o!|::44555555Cnhhyssu¬m¬wp
65 cmnN⊃{U6}\εuIiiI7(≡|4N↔uN≡k|kcN)xN¬JM|βi|β0N)2|gx|↔s|4α+↓|4|
65 ↔a|↔k|uc|)x|¬AM|βi|β1|)↑6gx|↔sS4α+↓|44¬BN4|¬ON4|¬ON4α~↓*444↔≡
65 U↔≡KUkC()F¬JMNβi|βt|)↑←gxF↔↔↔←;↓J**Kπ'nnmncjrciss
66 vgmpjgatenfrom the term corresponding to |εM|βi|βj
72 |[to thystervmcvgrjsqvmfkcvvhom|\MUkC(*2*2↓↓↓↓((),|[7kfqws
74 hpckknmf hhissukm usxbuccvckjrriddnout in the
79 binary nk¬bercsyszex,,succksthys|\ε-][(sujjssxmfkjcuqpjrm.
81 P≥3Cf.n(4π).I*26 In partccular, the sum of all
88 the terms fxg |εjK44*/←↔***241→|[↓qplpnmohckjrry
92 uphoo a=dct the terms for |εj|4α=↓|40, |πso we
100 must have|'|ε&a|βiI44¬}C44↔≡KukC)x|¬AXNβi|β0←)*454536V¬F44}¬C
102 466UkC≤**UIi*2((((),!0→44}}S44i44}¬S46#[KJ(4):{**}[π!|9|4|1|1|1
102 In order to prove Theorem H, wesqould like tonshow
111 that in some seffssthss|\εh|[αxxgjupv∧wjksmmfc6nvckkrccngicn
114 hhenbcnjcynruvresdntatcon of |εn |πmusy be pqq
121 inn]`πnesuwhuuhpvf↔'' sbnqwsqakmhhom=≡ffa way
124 to tell at whicm syeqisakvhmxfhhyssshzjvxsssssfmpuwlpy
129 dntjcs tell at which step each of these terms
138 essentially enters the additionncmain.|'!|9|4|1|1|1Let
143 |εj |πbe a number between 1 and |εt. |πSince
152 |εM|β0|βj |πis empty and |εM|βr|βj|4α=↓|4M|βj
157 |πis nonempty, we can _nd the |ε⊂rst |πstep |εi
166 |πfor which |εM|βi|βj |πis not empty.|'!|9|4|1|1|1From
173 the way in which the |εM|βi|βj |πare de_ned,
181 we know thaz szeq |εi |πis a non-doubling; |εa|βi|4α=↓|4a|βi
189 |βα_↓|β1|4α+↓|4a|βu |πfor some |εu|4|¬W|4i|4α_↓|41.
193 |πWe also know that all the elements of |εS|βu.
202 |πWe will prove that |εa|βu |πmust be relatively
210 small compared to |εa|βi.|'!|9|4|1|1|1|πLet |εx|βj
216 |πbe an element of |εM|βi|βj. |πThen since |εx|βj|4|¬A|4S|βu
223 , |πthere is some |εv |πfor which |εx|βj|4|¬A|4M|βu|βv.
231 |πIt follows that|'{A6}|εd|βi|4α_↓|4d|βu|4|¬Q|4m,|J!(45)|;
235 {A6}|π⊗i.e., at least |εm|4α+↓|41 |πdoublings
240 occur between steps |εu |πand |εi. |πFornif |εdSβi|4α_↓|4d|β
247 uS4|¬E|4., |πLemma K tewlssussthaw |ε*/¬{dSβjF4α≠↓←4&SIvC¬}C4
251 4}}Q467);|[[yfcks|\*2V44***2.|[α}qh hpis isicmpossible
254 because |εM|βu|βj |πis empty by our cvoccesmxfszeqi|≥=#[,'|:
260 :4455P5P5[↓Wlpswwxxfmtsnof |εS|βu |πare less
264 than or equaw to |ε_Sβ1|4α~↓**4d|βiI4≠↓|4≠FIi#,|π(Xgcikf|≥*2X4
268 4}}U4*/sIuu44*4)Y4*/SIii [↓kff I≤x|4|¬Q|4e|β1|4α+↓|4d|βi|4α_↓|4
270 d, |πthen |εx|4|¬A|4M|βu|β0λ|[≠kff|≥*2X44¬}U47MIiII1→
273 [αxy)5();sxm Lemma K implies that |¬G|εd|βi|4α_↓|4d|βu|¬G|4|
278 ¬W|4m, |πconoradicoingc(5).ICnfkkv.,hhpisijg¬kmdnt
280 vroves that |εM|βi|β0 |πhas no elements inncommomnwith
287 |εS|βu,,|π?S|βu, |πso |εM|ur|)(iα_↓1)0|)|4α=↓|4M|βi|β0.
290 |πFrom (44) we have |εa|βi|βα_↓|β1|4|¬R|42|ur|≤l(a|βi)|)|),
295 |πand therefore |εstep i is a small step.|'!|9|4|1|1|1|πWe
304 can now deduce what is probably the key fact
313 in this entire proof: |εAll elements of S|βu
321 are in M|βu|β0. |πFor if not, let |εx |πbe an
331 element of |εS|βu |πwith |εx|4|=|↔6|¬A|4M|βu|β0.
336 |πSince |εx|4|¬R|40, |π(40) implies that |εe|β1|4|¬R|4d|4α_↓
341 |4d|βu, |πhence|'{A6}|π|εe|β0|4|¬E|4r|4α=↓|4f|4α+↓|4d|4|¬E|4
343 3.271(t|4α_↓|41)|4α+↓|4e|β1|4α+↓|4d|βu.|;{A6}|πBy
345 hypothesis (43), this implies |εd|βu|4|¬Q|4e|β1.
350 |πBut |εd|βu|4|¬A|4S|βu |πby (41), and it cannot
357 be in |εM|βi|β0, |πhence |\≤Fβu|4|¬DS4e|β1|4α+↓|4d|βi|4α≠↓N4
361 dN4|¬D|4e|β1, |πa contradiction.|'!|9|4|1|1|1Going
365 back to our element |εx|βj |πin |εM|βi|βj, |πwe
373 have |εx|βj|4|¬A|4M|βu|βv; |πand we have provedfthat
379 |ε#|4α≡↓*440.,|ππhejjfxgj↔,xxysqquzignn(**0)↔a∧jun,]'{A6}F≥&e|
379 β0←4α+↓←4-Fβu|4α_↓|4dF4|¬R|4x|βj|4|¬Q|4e|β0|4α+↓|4d|βu|4α_↓|
379 4d|4α_↓|4m.|J!(44)|;{A6}|π!|9*34455145xgcuwlp|≥≤K4α*245#]42/]4
380 #]4.]4#]4/]4∀ |π≤wshq¬ksfdzzjvvcfdfuunk¬xbjc|≥*2XIjk|[(uwpufx
381 qcvv(4*2),ukffuusx¬wlpsyzqp \≥i [↓whiqpcchn(in
384 fome sense) the term |ε2|ure|βj|)|) |πin |εn
391 |πhas entejddficoonthysujdkppvmncvquc..IKf≠|\≤K44*/*/*4≡*24**kC¬F
392 , Nπthe step |εi |πat which thiu occujkscannoo
400 be thyssu¬xsfxgcxbohh|\≤k M↓knf |≤kN¬S; |πfor
405 (44) would tell us that |ε*3¬{x|βj|4↓≠↓|4xFUkC)≠S¬KS((}}V44}}
410 Q47.,|[↓qppwsswwfxfmhsnmf |εM|βi|βj |πand |εM|ur|)ij|¬S|(?|π
413 musz diεM|ur|)ij|¬S|) |πmust di=er by more than
420 |εm, |πsince |εe|βj |πand |εe|ur|)j|¬S|) |πare
426 so far apart. Therefore the chain contains at
434 least |εt |πsmall steps, but this is a contradiction.|'
443 |'|≡T|≡h|≡e|≡o|≡r|≡e|≡m |≡F (W. Hansen).|'{A6}|εl(2|gA|4α+↓|
448 4xy)|4|¬E|4A|4α+↓|4|≤n(x)|4α+↓|4|≤n(y)|4α_↓|41,!!|πif!!|ε|≤l
448 (x)|4α+↓|4|≤l(y)|4|¬E|4A.|J!(45)|;{A6}|π|εProof.|9|4|πAn
450 addition chain (which is |εnot |πa star chain
458 in general) may be constructed by combining the
466 binary method and the factor method. Let |εx|4α=↓|42|gx|r1|4
473 α+↓|4|¬O|4|¬O|4|¬O|4α+↓|42|gx|ru, y|4α=↓|42|gy|r1|4α+↓|4|¬O|
474 4|¬O|4|¬O|4α+↓|42|gy|rv, |πwhere |εx|β1|4|¬Q|4|¬O|4|¬O|4|¬O|
476 4|¬Q|4x|βu|4|¬R|40, y|β1|4|¬Q|4|¬O|4|¬O|4|¬O|4|¬Q|4y|βv|4|¬R
477 |40.|'!|9|4|1|1|1|πThe _rst stepssof theschain
482 form sukcessuvjspgwerfsof 2, ufoil 2←gA|gα_↓|gy|r1
487 is reached; in between these steps, thesvaluess|ε2|gxFru|rα≠
493 ↓*4r1←4α+↓|426gxFru↔,66vxXrkSrα≠↓*4r2]4α~↓*442]gxXrkScα≤↓*4r3←4α
493 ~↓*4426v¬Xck≡]4#[4#[4#[4/,|[≠kff|ε)x|[≤jjsicfsjgzdficnhhysuqp
493 vgvvcuwzsppwkks).UKxzjcuucvqucnuqphom Q≤6NgANgα≠↓|gy|ri|4α+↓
494 |4x(2|gy|r1| the appropriate places. After a
499 chain up to |ε2|gA|gα_↓|gy|ri|4α+↓|4x(2|gy|r1|gα_↓|gy|ri|4α+
502 ↓|4|¬O|4|¬O|4|¬O|4α+↓|42|gy|ri|rα_↓|r1|gα_↓|gy|ri)
503 |πhas been formed, continue by adding |εx |πand
511 doubling the latter result |εy|βi|4α_↓|4y|βi|βα+↓|β1
516 |πtimes; this yields|'{A6}|ε2|gA|gα_↓|gy|ri|rα+↓|r1|4α+↓|4x(
519 2|gy|r1|gα_↓|gy|ri|rα+↓|r1|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|42|ury|β
519 iα_↓y|βi|βα+↓|β1|)|)).|;{A6}|πIf this construction
523 is done for |εi|4α=↓|41,|42,|4.|4.|4.|4,|4v,
527 |πassuming for convenience that |εy|βv|βα+↓|β1|4α=↓|40,
532 |πwe have an addition chain for |ε2|gA|4α+↓|4xy
539 |πas desired.|'|'!|9|4|1|1|1|πTheorem F enables
545 us to _nd values of |εn |πfor qqpch |εl(n)|4|¬W|4l|≤⊂(n),
554 |πsince Theorem H givds an ex¬licit value of
562 |εl|≤⊂(↔)?|πinncdjoaic cases),For example, let
566 |εx|4α=↓|42|g1|g0|g1|g6|4α+↓←41,λy|4α=↓|42←g2|g0|g3|g2←4α+↓|
566 41, |πafdflez |εn|4α≡↓|42|g6|g1|g0|g6|4α+↓|4xy|4α=↓|42|g6|g1
568 |g0|g6|4α+↓|42|g3|g0|g4|g8|4α+↓|42|g2|gπ|g3|g2←4α+↓|42]g3←g3
568 ←g14g664α∃↓|41#,|But Theorem H also aqplies↔,quth
573 |εm|4α=↓|4508, |πand this proves that |εl|≤⊂(n)|4α=↓|46110.|
578 '|π!|9|4|1|1|1Extensive computer calculations
582 have shown that |εn|4α=↓|412509 |πis the smallest
589 value with |εl(n)|4|¬W|4l|≤⊂(n). |πNo star chain
595 for this value of |εn |πis as short as the sequence
606 1, 2, 4, 8, 16, 17, 32, 64, 128, 256, 512, 1024,
618 1041, 2082, 4164, 8328, 8345, 12509) The brute
626 force mezhodsin thesprgoffof ThebrjxnCccvkqdfxbssxxeffddfxxy
629 cvmvqqzjcpvgggj¬nhomfdzzjvvcfsuwlp|\*2nsukvhhhqwh|\ε()(4*244≤¬
629 (n)|6α∩|43; Nπthis approach would also characterize
635 all |εn |πwith |ε|≤n(n)|4α=↓|45λ|πand |εl(,)*444=*/*4***2↓45P*2≤))
639 ).(([πHsssx¬wlwsyhsukvh|≥*2n|[7us5777774*2466V35V#44α↓I4:I4K¬M
639 I437.)|'|'|≡S|≡o|≡m|≡es|≡c|≡o|≡,|≡j|≡&S≡c|≡≤|**≡U≡≡C≡≡S**≡S***2[
641 ::4*/Wlhm¬¬vhiphqwuscjaafmkj∧le to guess at _rst
646 glance that |εl(n)*44α=↓|4l|≤⊂(n), |πweshu¬ksnm∧qssefnhhqah
650 hhusiis false. Another plausible conjecture [_rst
656 majd by A.λGoulard↔,andssuqpvxsd∧qy,`7vgv¬dd',nxy
659 E.nde Jonqui|=2eres in |εl'IIIIICICICICCCCCCccnnnnnnnnnnnnnn
662 nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
662 nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
662 nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
662 nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
662 nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
662 nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
662 nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
662 nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
662 nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
662 nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
662 nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
662 nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
662 nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
662 nnnnnnnnnnnnnnnnnnnnnnnnnnni*?*?d,,and suqposedwy
664 ``proved''nbx E. ddsJonqui|=2eres in |εl'Interm.
669 des Math. |π|≡2 (1895), 125<126] is that |εl(2n)|4α=↓|4l(n)|
676 4α+↓|41; |πa doubling step is so e∃cient, it
684 seems unlikely that there could be any shorter
692 chain for |ε2n |πthan to add a doubling step
701 to the shortest chain for |εn. |πBut computer
709 calculatiofymqsthat this conjecture also fails,
714 since |εl(191)|4α=↓|4l(382)|4α=↓|411. (A star
718 chain of length 11 for 382 is not hard to _nd;
729 e.g., 1, 2, 4, 5, 9, 14, 23, 46, 92, 184, 198,
741 382. |πThe number 191 is minimal such that |εl(n)|4α=↓|411,
750 |πand it seems to be very di∃cult to provd bxshakffhhqt
760 |εl(*5*5*2(4|¬}Q450;y|["hsscvmvqqzj⊃↔spvgoxfmxfhhpusfkkv.,uuucv
760 vuux∧kk¬gjkkkmmehmofuqhich will be sketched in
765 Section 7.2.2, involved a detailednsxaminjwivnnmff:\*/*3ckuss)
769 ))HHyssx¬wlwsshfxmkrnvalues of |εn |πsuch that
774 |εl(2n)|4α=↓|4l(n) |πare |εn|4α=↓←4191, 701,
778 743, 1111≥?|[D),G#,Hhqk∧bjcpvgvkdficnhhyspqqqjcccpzdfu∧bv¬sh
779 hhwhhhys thirdnmf these is a memmmmmmmmmmmmmmmmmmmmmmmmmmmmm
784 mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm
784 mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmxm
784 xmxmxxbxbbbbbbbbb Thurber proved in the paper
790 cited above that the third of these is a mxxxbjcmxnaknic≡≡cp
799 zsfjmily of such |εn, |πnamely 737|4|¬O|42|ε|gk|4α+↓|47
805 |πfor all |εk|¬R|40. |πIt seems reasonable to
812 conjecture that |εl(2n)|4|¬E|4l(n), |πbut even
817 this may be false. Kevin R. Hebb has shown that
827 |εl(n)|4α_↓|4l(mn) |πcan get arbitrarily large,
832 for all _xed integers |εm |πnot a power of 2
842 |ε[Notices Amer. Math. Soc. |π|≡2|≡1 (1974),
848 A<294]. The smallest case in which |εl(mn)|4|¬W|4l(n)
855 |πis |εl((2|g1|g3|4α+↓|41)/3)|4α=↓|415.|'|Ha*?*?*?{U0}{H10L12M2
folio 595 galley 2
857 9}|πW58320#Computer Programming!ch. 4!f. 595!g.
861 2|'{A6}!|9|4|1|1|1Let |εc(r) |πbe the smallest
867 value of |εn |πsuch that |εl(n)|4α=↓|4r. |πWe
874 have the following table:|'|'|∂!!|∂!!|∂!!|∂!!|∂!!!|∂!!|∂!!|∂
879 !!!!|∂|E|;|>|εr|;c(r)|;|;r|;c(r)|;|;r|;c(r)|;
889 >{A2}|>1|;|9|12|;|;|9|17|;|9|129|;13|;!|1|1607|;
898 >|>2|;|9|13|;|;|9|18|;|9|147|;|;14|;|9|11087|;
908 >|>3|;|9|15|;|;|9|19|;|9|171|;|;15|;|9|11903|;
918 >|>4|;|9|17←;|;10|;127|;|;16|;|9|13783|;>|>5|;
930 11|;|;11←;191|;|;17|;*39|16271←;>|>6N;19|;|;13N;37αH;:;18|;
940 *51233|;>4''|πFbrc|εr|4|¬DS411,λ|≥*2*2)↔|[#usaqprox¬vjzzwqysqqu
942 wphom|≥*2*2C4≤↓45*2(4(~↓4/*2C4≤↓46*2),|[≤kffhhpusfkkvhpwdfhomsqqk
942 kqwwpvmnxxyss¬¬jjwpipbvpwe that |εc(r) |πgrows
946 like the function |ε|≤f|gr) |π~kz thescjsuqlhmxfHHybgjxmfF)q
951 phh \*2nI***2I6c(r)) N[implies that |εr/|πlg|4|εc(⊃)|4|¬MN41
956 |π≠us|≥,N44}}M44}}(. [(S¬¬jjwppqbvpws hjvenconjectured
959 that |εc(r) |πis always a prime nuxbej;?x¬qh|\≡5(44515I4C¬MI
965 4777 Nπand |εc(18)|4α=↓|411|4|¬O|41021. |πPerhaps
969 no conjdkguresu∧b¬q ujdkppvmncvpucnsiis safe*3|'
973 ⊗|Y:44P5P5P1Ljxulatdfnvaluesnof |εl(n) |πshow
976 that this function is surprisingly smooth;λfor
982 sx¬¬vpw↔,|\ε())4*2I433 Nπfor!|9|4|1|1|1Tabulated
984 values of |εl(n) |πshow that this function is
992 surprisingly smooth; for example, |εl(n)|4α=↓|413
997 |πfor all |εn |πin the range 1125|4|¬E|4n|4|¬E|41148.
1004 |πThe computer calculations show that a table
1011 of |εl(n) |πmay be prepared for all |εn|4|¬E|41000
1019 |πby using the formula|'{A6}|εl(n)|4α=↓|4|πmin(|εln|4α_↓|41)
1023 |4α+↓|41,|4l)|4α_↓|4|≤d,|J!(46)|;{A6}|πwhere
1025 |εl|4α=↓|4|¬X |πif |εn |πis prime, otherwise
1031 |εl|4α=↓|4l(p)|4α+↓|4l(n/p) |πif |εp |πis the
1036 smallest prime dividing |εn; |πand |ε|≤d|4α=↓|41
1042 |πfor |εn |πin Table 1, |ε|≤d|4α=↓|40 |πotherwise.|'
1049 {A12}|∨T|∨a|∨b|∨l|∨e|4|4|∨1|;{A2}{H9L11}|πVALUES|9OF|9|εn|9|
1050 πFOR|9SPECIAL|9ADDITION|9CHAINS|;{A2}|∂!!|9|1|1|1|∂!!!|∂!!!|
1051 ∂!!!|∂!!!|∂$!!|∂!!!|∂$!!|∪>!!|∂$!!|∪>!!|∪>!!|∪>
1055 !!|∪ISS;y|>←9*31236;*5775;↓<*54;7\*3;↓↑↑];\77];\555;715:676;737:
1056 7::*/14;:915;\>|44:H143M;\7↓*3;↑↓6;75|;↓\4;\554;\577;7*5:;6::75
1058 5::937::*/55::937:\> I4H:55\:Y*2337H)3α7|)359|;
1061 4"∩ ;∪#∩ hphm hn*1ot*1oo!⊗!`$8`$`3G|>|9|159|;203|;
1067 293|;359|;403|;453|;557|;623|;677|;717|;809|;
1076 849|;905|;>|>|9|177|;211|;311|;367|;413|;455|;
1086 561|;631|;683|;739|;813|;863|;923|;>|>|9|183|;
1096 213|;317|;371|;419|;457|;569|;637|;691|;741|;
1105 825|;869|;941|;>|>107|;227|;319|;373|;421|;479|;
1116 571|;643|;707|;749|;835|;887|;947|;>|>149|;229|;
1127 323|;377|;423|;503|;573|;645|;709|;759|;837|;
1136 893|;955|;>|>163|;233|;347|;381|;429|;509|;581|;
1147 659|;711|;779|;839|;899|;983|;>|>|'|'|'|'|'|'
1161 599|;>|'{H10L12}!|9|4|1|1|1Let |εd(r) |πbe the
1168 nkmber ofnsogutionf |εn |πto the equation |εl(n)|4α=↓|4r.
1175 |πWe have the following table:|'|'|∂!!|∂!!|∂!!|∂!!|∂$!|∂$!|∂
1181 !!|∂!!!|∂|ES;&|>|εr|;d(r)|;|;r|;d(r)|;|;r|;d(r)|;
1190 >{A2}|>1|;1|;|;|9|16|;←9*3115←;*3;11←;←9←1266];>
1197 ∂|426;6;:;:::577;:::5366;:;\36;:::5573N;\∂|437;↓7;:;:::5*5*3::
1197 ::5544:::\37::::57776:\>|>4|;5|;|;|9|19|;|9|178|;
1204 |;14|;138↑|;>|455::::::;11→:\376:;:≥55:)64%5:≥4N'|πSurewqy|ε
1208 ≠(≠*2)|[[¬uyhxbsuknicccjauucvvfkkcvpvmnnxf I≤c,
1210 |πbut there is no evident waysho prov¬shhis ssexccggqysuvvpw
1217 suussjgpvm,,m¬kvhpwssshomfdzzjvvcfshhhe asxmpootcc
1219 growth of |εd(r) |πfor large |εr.]'!|::44555555[πHysmmxyhfk¬
1224 m¬uspvgb∧lfm jbmuhijddition chains which i!|9|4|1|1|1|πThe
1229 most famous problem about addition chains which
1236 is still outstanding is the ``Scholz-Brauer conjecture,''
1243 which states that|'{A6|ε⊗l(2|gn|4α_↓|41)|4|¬E|4n|4α_↓|41|4α+
1246 ↓|4l(n).|J!(47)|;{A6}|πComputer calculations
1249 show, in fact, that equality holds in (47) for
1258 |ε1|4|¬E|4n|4|¬E|414; |πand hand calculations
1262 by E. G. Thurber [|εDiscrete Math. |π|≡1|≡3 (1975),
1270 to appear] have shown that equality holds also
1278 for |εn|4α=↓|415, 16, 17, 18, 20, 24, 32. |πMuch
1287 of the research on addition chains has been devoted
1296 to attempts to prove (47) addition chains for
1304 the number |ε2|gn|4α_↓|41, |πwhich has so many
1311 ones in its binary representation, are of special
1319 interest, since this is the worst case for the
1328 binary method. Arnold Scholz coined the name
1335 ``addition chain'' (in German) and posed (47)λas
1342 a problem in 1937 [|εJahresbericht der deuzschen
1349 Mjthexatikkj≠djjuccv¬kv#,|[#vwussII/,|[]≡44≡/(*5↓7*2↔,41↓**66)?
1349 UwkjddfX≠juujcpvgv¬dficn5*5↓↓;hhqwH]↓J**}\εlP*2≤*26VvN4↓≤45)44}¬
1349 SI6nI↓≠|45I6α∩↓I4pN≤⊂(n).NJ!(48)|;{A6}|π!|9*34|1|1455akfef,↔s
1350 hhybgjxxssym∧qhhqwh|\ε())ckknxbspwssshhqkn QεlN≤∩(n),
1352 |πso more work is de_nitelysnecessaj¬yicnorder
1357 to prove or disprove (47). As a step in thiusdkrjkgion,,Hakf
1366 sfnhqusfd_≡fdfhhyscvmckqphmxfukn|\εPV3α≡vquc,,|[↓qpcvhppuss,
1366 `αbzwwefn'' |εg-Nπchains and |εl|≤⊂-|πchains.
1370 In an |εl|g0-|πchain, certain ofsthe elexdnts
1376 ajj ufddjgicdd);hhsscvmfkppvmniushhqwh|\εUIiiI***2I4a|rj|4α+↓|
1377 4a|βk, |πwhere |εa|βj |πis the largest underlined
1384 elexent lesssthukn|\_UIj*2[]'|H9|4|1|1|1NπAs an
1387 example of an |εl|g0-|πchain (certainlysnot a
1393 mcccmal onf)),cvnfukdjC]↓{**}\ε⊂7,c6, 6,i7, <,
1397 1π, 1, 2, 4, 5,n8, 10, 12, 18;|J!(49)|;{A6}|πit
1406 is easy to verify that the di=erence between
1414 each element and the previous underlined element
1421 is in the chain. We let |εl|g0(n) |πdenote the
1430 minimum length of an |εl|g0-|πchain for |εn.
1437 |πClearly |εl(n)|4|¬E|4l|g0(n)|4|¬E|4l|≤⊂(n).|'
1439 |π!|9|4|1|1|1The chain constructed in Theorem
1444 F is an |εl|g0-|πchain (see exercise 22); hence
1452 we have |εl|g0(n)|4|¬W|4l|≤⊂(n) |πfor certain
1457 |εn. |πIt is not known whether or not |εl(n)|4α=↓|4l|g0(n)
1466 |πin all cases; if this equation were true, the
1475 Scholz-Brauer conjecture would be settled, because
1481 of another theorem due to Hansen:|'|'|≡T|≡h|≡e|≡o|≡r|≡e|≡m
1489 |≡G|≡.|9|4|εl|g0(2|gn|4α_↓|41)|4|¬E|4n|4α_↓|41|4α+↓|4l|g0(n)
1489 .|'|'Proof.|9|4|πLet |ε1|4α=↓|4a|β0, a|β1,|4.|4.|4.|4,|4a|βr
1493 |4α=↓|4n |πbe an |εl|g0-|πchain of minimum length
1500 for |εn, |πand let |ε1|4α=↓|4b|β0, b|β1,|4.|4.←4.|4,λbFβt|4α
1505 ≡↓*44,n|[~bsthe su¬fequefcdsof underlined elements.
1509 (We may assume that |εn |π∪ssufdejgpcdd.)↔Thsfnqasckkngjzhuk
1514 n|≥εPv3α*4[#vqucnfxgc|≥↓6vcN4≤↓**45∀|[≤usfxglg∧q:*3,↓{**}∧}5#77}
1514 }a*2)Y:P5Ccvpkde hhe |εl|g0(n) |πnumbers |ε2|ga|ri|4α_↓|41,
1519 |πfor |ε1|4|¬E|4i|4|¬E|4r, |πunderlined if and
1524 only if |εaSβi |π/usunddjgpcfd)]]'b)(:\Ccvqkdshhysnk¬xbjks|≥
1527 ↓6Vv**6V∧XCjK4↓↓45),|[(xgc \ε→44 N¬E|6j|4|¬W|4t
1530 |πand for |ε0|4|¬W|4i|4|¬E|4b|βj|βα+↓|β1|4α_↓|4b|βj↔,|[≠wliu
1532 fddjgicdd).((Hpusiusuuhoowwpmxf|\≤XIβ⊂5I6↓≠4x|β0|6α"I4|¬O|4|
1532 ¬O|4|¬O|4α+↓|4b|βt|4α_↓|4b|βt|βα_↓|β1|4α=↓←4,N4↓↓455|[,k¬xbj
1532 k))(]'c)|9|1|1Sort the numbers from (**) and (b)
1539 into ascendingnsequafck)[]↓{**}}C}}!|9|4|1|1|1We
1541 may easilysverifxsthat this givessan |εεIvπ-*4π/vuuc(;HHysnk¬
1545 xbjksmxfn(x)ijrs all equal to twice some other
1552 elemeft of (*2?or ())) furghyjvmgj↔,hhpusswwfmdnt
1557 is the preceding underlined elwxent..IKf|εa|βjK4α=↓|4~|βj|4α
1561 ~↓*44a|β≡,|[≤qsjjs \≤XIjk M7is the largest underlined
1567 element leeeseseseeeeeeeeeeeeeeeeeeee1We may
1570 easily verify that this gives an |εl|g0-|πchain:
1577 The numbers of (b) are all equal to twice some
1587 other element of (a) or (b); furthermore, this
1595 element is the preceding underlined element.
1601 If |εa|βj|4α=↓|4b|βj|4α+↓|4a|βk, |πwhere |εb|βj
1605 |πis the largest underlinddfewexefm less than
1611 |εa|βi, |πthen |εa|βk|4α=↓|4a|βj|4|¬E|4b|βj|βα+↓|β1|4α_↓|4b|
1613 βj, |πso |ε2|ga|rk(2|gb|rj|4α_↓|41)|4α=↓|42|ga|ri|4α_↓|42|ga
1615 |rk |πappears underlined in the chain, just preceding
1623 |ε2|ga|ri|4α_↓|41. |πSince 2|ε|ga|ri|4α_↓|41|4α=↓|4(2|ga|ri|
1625 4α_↓|42|ga|rk)|4α+↓|4(2|ga|rk|4α_↓|41) |πand
1627 both of these appear in the chain, we have an
1637 addition chain with the |εl|g0 |πproperty.|'|'
1644 !|9|4|1|1|1The chain corresponding to (49), constructed
1650 in the proof of Theorem G, is|'{A6}1, 2, 3, 6,
1661 12, 15, 30, 31, 60, 120, 240, 255, 510, 1020,
1671 1023, 2040,|'{A3}4080, 4095, 8160, 16320, 32640,
1678 65280, 130560, 261120, 26214∩. ?*?*?*?*?{U0}{H10L12M29}|πW58320#
folio 598 galley 3
1682 Computer Programmcng∨cm. 4!f).5:98g.n36N,{{6}o|∨E|∨X|∨E|∨R|∨
1684 C|∨I|∨S|∨E|∨S|'|'{H9L11}|9|1|≡1|≡.|9|4|ε[|*/|↔O|↔C|\]|9|πWhat
1686 is the value of |εZ |πwhen Algorithm A termcnkwzs?|'
1696 ↓{↓¬|::5⊂|≡**6≡*2[::44\[*/*/*4P*4(M\]::[↓{cpzsuu }¬m}¬iN¬x
1698 vrogram for Algorithm A, to calckwate |ε)FgcN4←πmod|4←≥εq|[∩
1704 vv¬fnicmz∧∧jks \*2n [↓knd |εx, Nπwhere |εw |πis
1711 the word suze. Assume thaz |¬x|¬kI¬¬fhqushhysx¬ckj¬ymvqjjwpv
1716 mfs C¬sC¬l|¬b, |¬j|¬a|¬e, etc., which aresdescribed
1722 in SSktionn{U0}{H10L12M29}|πW58320#Computer Programming!ch.
folio 600 galley 4
1725 4!f. 600!g. 4C|'{A6}|π{H9L11}|≡2|≡8|≡.|9|4|ε[M|*/|↔L|↔c|\]|9(
1728 |πA. Sch|=4onhage.) The object of this exercise
1735 is to give a fairly short proof that |εl(n)|4|¬R|4|≤l(n)|4α+
1743 ↓|4|πlg|4|ε|≤n(n)|4α_↓|4O(|πlog|4log|≥1|ε|≤n(n)|4α+↓|41)|≥2.
1743 |π(a) When |εx|4α=↓|4(x|βk|4.|4.|4.|4x|β0, x|βα_↓|β1|4.|4.|
1747 4.)|β2 |πand |εy|4α=↓|4(y|βk|4.|4.|4.|4y|β0,
1750 y|βα_↓|β1|4.|4.|4.)|β2 |πare real numbers written
1755 in binary notation, let us write |εx|4|↔Y|4y
1762 |πif |εx|βj|4|¬E|4y|βj |πfor all |εj. |πGive
1768 a simple rule for constructing the smallest number
1776 |εz |πwith the property that |εx|¬S|4|↔Y|4x |πand
1783 |εy|¬S|4|↔Y|4y |πimplies |εx|¬S|4α+↓|4y|¬S|4|↔Y|4z.
1786 |πDenoting this number by |εx|4|¬6y, |πprove
1792 that |ε|≤n(x|4|¬6y)|4|¬E|4|≤n(x)|4α+↓|4|≤n(y).
1794 |π(b) Given any addition chain (11) with |εr|4α=↓|4l(n),
1802 |πlet |εd|β0, d|β1,|4.|4.|4.|4, d|βr |πbe de_ned
1808 as in (37), andfde_ne the sequence |εA|β0, A|β1,|4.|4.|4.|4,
1815 A|βr |πby the following rules: |εA|β0|4α=↓|41;
1822 |πif |εa|βi|4α=↓|42a|βi|βα_↓|β1 |πthen |εA|βi|4α=↓|42A|βi|βα
1825 _↓|β1; |πif |εa|βi|4α=↓|4a|βj|4α+↓|4a|βk |πfor
1829 some |ε0|4|¬E|4k|4|¬W|4j|4|¬W|4i, |πthen |εA|βi|4α=↓|4A|βi|β
1832 α_↓|β1|4|¬6A|βi|βα_↓|β1/2|urd|βjα_↓d|βk|)|).
1833 |πProve that this sequence ``covers'' the given
1840 chain, in the sense that |εa|βi|4|↔Y|4A|βi |πfor
1847 |ε0|4|¬E|4i|4|¬E|4r. |π(c) Let |ε|≤d |πbe a positive
1854 integer (to be selected later). Cjll the nondoubling
1862 step |εa|βi|4α=↓|4a|βj|4α+↓|4a|βk |πa ``baby
1866 step'' if |εd|βj|4α_↓|4d|βk|4|¬R|4|≤d, |πotherwise
1870 call it a ``close step.'' Let |εB|β0|4α=↓|41;
1877 B|βi|4α=↓|42B|βi|βα_↓|β1 |πif |εa|βi|4α=↓|42a|βi|βα_↓|β1;
1880 B|βi|4α=↓|4B|βi|βα_↓|β1|4|¬6B|βi|βα_↓|β1/2|urd|βjα_↓d|βk|)|)
1880 |π∪f |εa|βi|4α≡↓*44_Sβj|4α+↓]4_Uβkn|π/usasxj∧xsszep;
1883 afd |εBNβi|4α≡↓*44←≤⊃(↑↓Fβi|βα≠↓|β1))|π"ohej∧uue↔,qqyjjs|ε*/*2≤
1884 ))↔|[7ushhyspwauy nk¬xbjc|\≥y|[)ukvhhhqwh|\*2*266V∧S44*4(Y4\y|[
1885 (xgc \*5→44}¬S4*/s44}¬SI4}≤x. NπSmow that |εA|βi|4|↔Y|4B|βi
1890 |πand |ε|≤n(B|βi)←4|¬E|4(1|4α+↓|4|≤-kNβi)2|g∧XCci|π↔brc→→44¬
1891 }S44\≥I44}}S46/,|[↓qyjjs|\≤XIii [↓kff \*2cIii|[3jsqqkvpv¬aqyn
1893 dfnote the number of baby steps and close steps|4|¬DS4|εi.,[
1901 [int|*/\*3\?|π*4ym∧uthuwhhhss53↔sicn|\↓XIii|[↓qpqajcicncvmfskku
1901 hcvsx∧gmcksnof size |¬R|ε1|4α+↓|4|≤dc|βi.] |π(d)
1905 We now have |εl(n)|4α≡↓&|4r|4α≡↓*44*2XirC4~↓4/CβrC4α↓**4≡FIrc|[
folio 604 galley 5
1908 ↓kff{U0}{H10L12M29}|πW58320#Computer Programming!ch.
1910 4!f. 604!g. 5C|'{A6}!|9|4|1|1|1Several generalizations
1915 of Horner's rule have been suggested. Let us
1923 _rst consider evaluating |εu(z) |πwhen |εz |πis
1930 a complex number, while the coe∃cients |εu|βk
1937 |πare real. Complex addition and multiplication
1943 can obviously be reduced to a sequence of ordinary
1952 operations on real numbers:|'{A6}|h|∂complex|4α+↓|4complex!!
1956 |∂requires!!|∂4 multiplications, 2 additions|E|n|;
1960 |Lreal|4α+↓|4complex|Lrequires|L1 addition>|Lcomplex|4α+↓|4c
1962 omvlexFLrjqqirdsSL2/addctiomf*/|Lreal|4α⊗↓|4/omvlexFLrjquirds
1962 SL2λmkwliplicationf>|LcomvlexN4α'↓N4comvlex|Lrdquires|L4∪mkw
1963 liplicjwions,n2,additionf>⊗|L|Lor|L3 mkltiplications,n5
1966 additions>{A6}(See exerccses41.,Su¬bgjkvivnniushsjjscvnfukdj
1968 jdfuusikfiphqwjjssqquv∧wwfmhhomujdkhpvm.)nThyjjfbrdsHmrnej⊃↔
1968 sckqes(*2↔uussssuphyjc|ε4/N4≤↓N42n|π.kqlppppckwpvmf
1969 ufdn|ε3nN4α≠↓≠|42,|π≤jdctpvnfsmgc|≥↓#N4α≤↓**45∀|[[¬qlipppckwp
1969 vmfsukff|\6N4↓≤455 [↓jdkppcons om fvaluate |εu(z)
1974 |πwhen |εz|4α=↓|4x|4α+↓|4iy |πis complex. An
1979 alternative procddkjdsfbr e¬jwuawicvc|≥=)X4α↓44q))|[7ushompw
1981 zh]≤{**}\ε|εa|β1|4α=↓|4u|βn,!!b|β1|4α=↓|4u|βn|βα_↓*3β1,!!r|4α=
1981 ↓|4xS4α+↓|4x,!!s|4α=↓←4x|g264↓∃↓*34≥Sv2)*3;{*/}a|βj|||||||||||I
1981 |4I444444444444444444444444444444444444444444444444444444444
folio 609 galley 6
1981 44444444*?*?*?{U0}{H10L12M29}|πW58320#Computer Programming!ch.
1983 4!f. 609!g. 5C|'{A6}|≡A|≡d|≡a|≡p|≡t|≡a|≡t|≡i|≡o|≡n
1987 |≡o|≡f |≡c|≡o|≡e|≡∃|≡c|≡i|≡e|≡n|≡t|≡s|≡.|9Let
1989 us now return to our original problem of evaluating
1998 a given polynomial |εu(x) |πas rapidly as possible,
2006 for ``random'' values of |εx. |πThe importance
2013 of this problem is due partly to the fact that
2023 standard functions such as sin|4|εx, |πcos|4|εx,
2029 e|gx, |πetc., are usually computed by subroutines
2036 which rely on the evaluation of certain polynomials;
2044 these polynomials are evaluated so often, it
2051 is desirable to _nd the fastest possible way
2059 to do the computation.|'!|9|4|1|1|1Arbitrary
2064 polynomials of degree _ve and higher can be evaluated
2073 with less operations than Horner's rule requires,
2080 if we _rst ``adapt'' the coe∃cients |εu|β0, u|β1,|4.|4.|4.|4
2087 , u|βn. |πSuch an adaptation process might involve
2095 a fairly complex calculation, as explained below;
2102 but the preliminary calculation is not wasted,
2109 since it must be done only once while the polynomial
2119 will be evaluated many times. For examples of
2127 ``adapted'' polynomials for standard functions,
2132 see V. Ya. Pan, |εUSSR Computational Math. and
2140 Math. Physics |π|≡2 (1963), 137<146.|'!|9|4|1|1|1The
2146 simplest case for which adaptation of coe∃cients
2153 is helpful occurs for a fourth degree polynomial:|'
2161 {A6}|εu(x)|4α=↓|4u|β4x|g4|4α+↓|4u|β3x|g3|4α+↓|4u|β2x|g2|4α+↓
2161 |4u|β1x|4α+↓|4u|β0,!!u|β4|4|=|↔6α=↓|40.|J!(8)|;
2162 {A6}|πThis equation can be rewritten in a form
2170 suggested by Motzkin,|'{A6}|εy|4α=↓|4⊗()|4α+↓|4←≤_Sβ0))|4α~↓
2173 **4⊗|≤≠Ui1#`!u))*44α≡↓*444≥\()Y4~↓4*2F4α~↓N4|≤≤Ui2)x|4α~↓*44|≤aSβ
2173 3)|≤≠Ui4,|J!(α)←;{A**Fπ'fbrcsuutab∧yy``jdjpted-',cod∃≡cents
2174 |ε*3≤j|β0, |≤_Sβ1, |≤_|β2,λ|≤≠Sβ3,λ|≤≠Sβ4#,|ππhescomvutazionn
2176 icnthissfbgvmmbvcokuwy invogves three multiplications,
2180 _ve additions, and one instruction to store the
2188 partial result |εy |πinoontexviszorjg∧;?bx comvujcsxnntonHor
2192 ndj⊃↔srkwa↔,washq¬kshgjjddfuumkqlipppckwivmnfxrcaknujdkppvmn
2192 ukffuusyorccv..Svdfnthpsscomvurjzivdwyssmallisa¬ingksisswbrg
2192 hhqqipasiffhhyspvgqxmmvuwiiushomxbss¬¬wquwzdfmxxzf..((xfcv¬k
2192 ks↔,ikfhhyshpvxsfxgcm¬qlppppckwpvmniuscvmvqjj∧∧ws
2193 omhhys pcxsnfor jdkitcon, (α) gives no improvement;
2200 we will see that a general fourth-degree polyfomcawiuwwaqssc
2207 jquucjssuw pwauyhsuvvhhujcphmxzpccmvqjjwpvmfsicnipyss¬¬wquwp
2208 vm.))]'!|9|4|1|1|1By comparing coe∃cients in
2212 (8) and (9), we obtain formkwassfbr cvmvuqicgchhys|≥*/*2≤UIj≠]
2218 [(sicnhzjvxsmxfhhys \≥u|rk,N(s:N'{J6}|ε|≠Sβ0|44←f↓5F↓36((UIβ
2219 ∩7≡uI∪44↓≠I47),!|K≤b|4α=↓|4u|β2/u|β4|4α_↓|4|≤a|β0(|≤a|β0|4α+
2219 ↓|41)↔$!|≤a|β1←4α=↓←4=Sβ1/=Sβ4←4α≠↓44≤≠Uβ1←*2~↔N;{*/¬|≤UI26444
2219 V≤x4↓≤I62|≤a|β1,!!|≤a|β3|4α=↓|4u|β0/u|β4|4α_↓|4←≤a|β1(|≤a|β1
2219 |4α+↓|4|≤a|β2),!!|≤a|β4←4α=↓←4u|β4#]JD(10)*4:↓J**}[πUsuvvpwa*1c
2219 kvyxx↔,qqpcch ¬¬apuates a fourth-degree
2228 i pippppppppppppp|*2a|β2←4↓=↓|4←≤~|4α_↓*442|≤a|β1,!!|≤j|β3|4α≡
2229 ↓|4=Ui0/k|β444≤↓N4|≤j|β1(N≤a|β1|4α+↓|4|≤a|β2),!!|≤a|β4|4α=↓|
2229 4u|β4.|J!(10)|;{A6}|πA similar scheme, which
2234 evaluates a fourth-degree pogqxomialhin the same
2240 number of steps as (9), appears in exercise 18;
2249 this alternative method will give greater numerical
2256 accuracy than (9) in certain cases, although
2263 it yields poorer accuracy in other cases.|'!|9|4|1|1|1Polyno
2270 mials which arise in practice often have a rather
2279 small leading coe∃cient, so that the division
2286 by |εu|β4 |πin (10) leads to instability. In
2294 such a case it is usually preferable to replace
2303 |εx |πby |ε|¬Gu|β4|¬G|4|g1|g/|g4x |πas the _rst
2309 step/,reducing (8) to |¬N a monic polynomial.
2316 A similar transformation applies to polyxmmvulysoffhigmejndd
2321 ∧rdes),Thissidda issfkesto C#,T. Fikes|ε[6ACMn|π|≡1←≡αλ(1967
2324 )↔,175<378],,wyo hassprdsentedfseverjl inoerdstingnexamples.
2326 |'!|9|4|1|1|1Anx polynomial of the _fth degree
2333 may be evaluated using four multiplications,
2339 six additions, and one storing, by using the
2347 rule |εu(x)|4α=↓|4U(x)x|4α+↓|4u|β0, |πwhere |εU(x)|4α=↓|4u|β
2350 5x|g4|4α+↓|4u|β4x|g3|4α+↓|4u|β3x|g2|4α+↓|4u|β2x|4α+↓|4u|β1
2351 |πis evaluated as in (9). Alternatively, we can
2359 do the evaluation with four multiplications,
2365 _ve additions, and three storings, ifsthe calculations
2372 take the form|]'{A6}|ε*?*?*?*?{U0}{H10L12M29}|πW58320#Computer
folio 611 galley 7
2375 Programming!ch. 4!f. 611!g. 7C|'{A6}!|9|4|1|1|1Another
2380 method for doing sixth-degree equations has been
2387 suggested by V. Ya. Pan [see L. A. Lyusternik,
2396 O. A. Chervonenkis, A. R. Yanpol'skii, |εHandbook
2403 for Computing Elementary Functions, |πtr. by
2409 G. J. Tee (Oxford: Pergamon, 1965), 10<16]. Pan's
2417 method requires one more addition operation,
2423 but it does not involve _rst solving a cubic
2432 equation in the preliminary steps. We may proceed
2440 as follows:|'{A6}|εz|4α=↓|4(x|4α+↓|4|≤a|β0)x|4α+↓|4|≤a|β1,!!
2442 w|4α=↓|4z|4α+↓|4x|4α+↓|4|≤a|β2,|;{A4}u(x)|4α=↓|4|≥1((z|4α_↓|
2443 4x|4α+↓|4|≤a|β3)w|4α+↓|4|≤a|β4)z|4α+↓|4|≤a|β5|≥2|≤a|β6.|J!(1
2443 6)|;{A6}|πTo determine the |ε|≤a'|πs, once again
2450 divide the polynomial by |εu|β6|4α=↓|4|≤a|β6
2455 |πso that |εu(x) |πbecomes monic. It can then
2463 be veri_ed thaw |ε|≤a|β0|4α=↓|4u|β5/3 |πand that|'
2469 {A6}|ε|≤a|β1|4α=↓|4(u|β1|4α_↓|4|≤a|β0u|β2|4α+↓|4|≤a|=|β0|g2u
2469 |β3|4α_↓|4|≤a|=|β0|g3u|β4|4α+↓|42|≤a|=|β0|g5)/(u|β3|4α_↓|42|
2469 ≤Note that Pan's method requires that the denominator
2477 does not vanish; i.e.,|'{A6}|ε27u|β3u|=|β6|g2|4α_↓|418u|β6u|
2481 β5u|β4|4α+↓|45u|=|β5|g3|4|=|↔6α=↓|40;|J!(18)|;
2482 {A6}|πin fact, this quantity should not be so
2490 small that |ε|≤a|β1 |πbecomes too large. Once
2497 |ε|≤a|β1 |πhas been determined, the remaining
2503 |ε|≤a'|πs may be determined from the equations|'
2510 {A6}|ε|≤b|β1|4α=↓|42|≤a|β0,!!|≤b|β2|4α=↓|4u|β4|4α_↓|4|≤a|β0|
2510 ≤b|β1|4α_↓|4|≤a|β1,!!|≤b|β3|4α=↓|4u|β3|4α_↓|4|≤a|β0|≤b|β2|4α
2510 _↓|4|≤a|β1|≤b|β1,|;{A4}|≤b|β4|4α=↓|4u|β2|4α_↓|4|≤a|β0|≤b|β3|
2511 4α_↓|4|≤a|β1|≤b|β2,|;{A4}|≤a|β3|4α=↓|4|f1|d32|)|≥1|≤b|β3|4α_
2512 ↓|4(|≤a|β0|4α_↓|41)|≤b|β2|4α+↓|4(|≤a|β0|4α_↓|41)(|≤a|=|β0|g2
2512 |4α_↓|41)|≥2|4α_↓|4|≤a|β1,|;{A4}|≤a|β2|4α=↓|4|≤b|β2|4α_↓|4(|
2513 ≤a|=|β0|g2|4α_↓|41)|4α_↓|4|≤a|β3|4α_↓|42|≤a|β1,!!|≤a|β4|4α=↓
2513 |4|≤b|β4|4α_↓|4(|≤a|β2|4α+↓|4|≤a|β1)(|≤a|β3|4α+↓|4|≤a|β1),|;
2514 {A4}|≤a|β5|4α=↓|4u|β0|4α_↓|4|≤a|β1|≤b|β4.|J!(19)|;
2515 {A6}|π!|9|4|1|1|1We have discussed the cases
2520 of degree |εn|4α=↓|44, 5, 6 |πin detail because
2528 the smaller values of |εn |πarise most frequently
2536 in applications. Let us now consider a general
2544 evaluation schemd fxrc|ε)Nπ"hhfd∧gjespvgqfmmcuwq↔,qqpcvhuwww
2546 qyshakkss|≥\.∩v/66.3P4~↓466|[.¬qlppppckwpvmfsukff|\*2n
2547 Nπjdkipcmnf.N'N'|≡T|≡h|≡e*?a general evaluation
2550 scheme for |εn|πth degree polynomials, which
2556 always takes |ε|"ln/2|"L|4α+↓|42 |πmultiplications
2560 and |εn |πaddutions.N'|'|≡T|≡h|≡e|≡o|≡r|≡e|≡m
2564 |≡E|≡.|9|4|εEvery nth degree polynomial (1) with
2570 real coe∀cients, |εn|4|¬R|43, |π|εcan be evaluated
2576 by the scheme|'{A6}|εy|4α=↓|4x|4α+↓|4c,!!w|4α=↓|4y|g2;|;
2580 {A4}z|4α=↓|4(u|βny|4α+↓|4|≤a|β0)y|4α+↓|4|≤b|β0!(n|4|πeven),!
2580 !|εz|4α=↓|4u|βny|4α+↓|4|≤b|β0!(|εn|4|πodd);|;
2581 {A4}|εq(x)|4α=↓|4|≥1|¬O|4|¬O|4|¬ON4((z(w|4α_↓|4|≤a|β1)N4α"↓N
2581 4|≤b|β1)(w|4α_↓|4|≤a|β2)|4α"↓|4|≤b|β2)|4|¬O|4|¬O|4|¬O|≥2(w|4
2581 α_↓|4|≤a|βm)|4α+↓|4|≤b|βm;|J!(20)|;{A6}|π|εfor
2583 suutabwe real paramezers c, |≤a|βk and |≤bSβk,
2590 whejd |εm|4α=↓|4|"ln/2|"L|4α_↓|41. In fact it
2595 is possible to select these paramezersssbnthaw
2601 |≥&|≤≤FimN4α≡↓**45.],]]'|≥\roof)]9*344[3az uus=≠ky
2603 sx¬¬vcfshhyscccck¬xywkckssukfdjr whcch the |εN≤a'|πs
2607 and |ε|≤b'|πs cak be chmfen in (20), ikf|εc |[/us_)dd(:paz|]
2615 ↓{**}\εp())4*24*/*2(X4↓≤46*2)4*24*/uIcnxCgn|4α+↓|4a|βnp(x)*44α=↓←4=)
2615 |4α≠↓←4/)←4α=↓|4a|βnx|gn|4α∃↓|4aSβcNi↓≠↓i1)|gnNvα≠↓*4g344α+↓|
2615 4|¬ON4|¬O|4←¬O|4α+↓|4a|β1x|4α+↓|4a|β0.|J!(21)|;
2616 {A6}|πWe want to show that |εp(x) |πhas the form
2625 |εp|β1(x)(x|g2|4α_↓|4|≤a|βm)|4α+↓|4|≤b|βm |πfor
2627 some polynomial |εp|β1(x) |πand some constants
2633 |ε|≤a|βm, |≤b|βm. |πIf we divide |εp(x) |πby
2640 |εx|g2|4α_↓|4|≤a|βm, |πwe can see that the remainder
2647 |ε|≤b|βm |πis a constant only if the auxiliary
2655 polynomial|'{A6}|εq(x)|4α=↓|4a|β2|βm|βα"↓|β1x|gm|4α+↓|4a|β2|
2656 βm|βα_↓|β1)|gm|gα_↓Ng3|4α+↓|4|¬O|4|¬O|4←¬O|4α+↓|4a|β1,|J!(22
2656 )|;{A6}|πformed from every odd-numbered coe∃cient
2662 of |εp()),,|πis a muwtpple of |εx|4α_↓|4|≤a|βm.
2668 |πConvdrfely, if |εq(x)λ|πhas |εx|4α≠↓*44←≤≠Sβm
2672 |π≠usasfjkvog/,hhsfn|≥≥))(4*2(4∀Pi1))()XV364≤↓44≤UIv)(4α≤44≤X
2672 Iv.,|[(xgcsxmxscvmfywkmh U≥**≤xIcm, N3qhcch may
2676 be determined by division.|'!|9|4|14541*/uvcpwjgq),qwsqwkmh|\
2680 ≥pI⊂()) [πomhq¬¬s hhsnform |εp|β2(x)(x|g2|4α_↓|4|≤a|βm|βα_↓|
2683 β1)|4α+↓|4|≤bFβm|βα_↓←β1,,|π≠fdfthiusiushhyssu¬xsuussuqqcvvh
2683 hqwh|≥≥()*2(X4↓↓44≤auIv)) [7usuunvultiple of |εx|4α_↓|4|≤a|βm
2686 |βα_↓|β1; |πfor if |εq|β1()) |πis thespolynomcuwpcgrrjsqvmfk
2691 cvvhom|\≥pI⊂()) [↓us \≥¬(x) M7corresponds to
2696 |εp(x), |πwe have |≥≥|β1(x)|4α=↓|4q(x)/(x|4α_↓|4|≤a|βm).
2700 |[7vmminkucvvicnhhessu¬xsqwq),qws=≡ffhhqwhhhyspqjj¬xzzjks
2701 \≥≤uIβ3, N≤*1bIβ3,|4.|4.|4.|4, |≤a|βm, |≤b|βm
2705 |πwillisxist if and only if|'{A6}|εq()(44*/UI26IvMI↓α↓I1(x4**↓
2710 ≠I4C≤u|β3)|4N¬O|4|¬O|4|¬O|4(x|4α_↓|4|≤a|βm).|J!(23)|;
2711 {A6}|πICnmohyjcq∧gjff, uphyjc|≥≥*2())|[7us|∂|πeither!!|∂|ε|≤l
2712 |βi|4α=↓|4(|→|¬N|≤l|βj)|4|≤∪|4|≤l|βk,!!|∂0|4|¬E|4j,|4k|4|¬W|
2712 4i|;{A4}|L|L|ε|≤l|βi|4α=↓|4|≤a|βj|4|≤∪|4|≤l|βk,|L0|4|¬E|4k|4
2713 |¬W|4i.|J!(25)>{A6}|πHere ``|≤∪'' denotes any
2718 of the three operations ``α+↓'', ``α_↓'', or
2725 ``α⊗↓'', and |ε|≤a|βj |πdenotes a so-called ``parameter.''
2732 Steps of the _rst kind are called |εchain steps,
2741 |πand steps of the second kind are called |εparameter
2750 steps. |πWe shall assume that a di=erent parameter
2758 |ε|≤a|βj |πis used in each parameter step; if
2766 there are |εs parameter steps, they should involve
2774 |ε|≤a|β1, |≤a|β2,|4.|4.|4.|4, |≤a|βs |πin this
2779 order.|'!|9|4|1|1|1It follows that the polynomial
2785 |εu(x) |πat the end of the chain has the form|'
2795 {A6}|εu(x)|4α=↓|4q|βnx|gn|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4q|β1x|4α
2795 +↓|4q|β0,|J!(26)|;{A6}|πwhere |εq|βn,|4.|4.|4.|4,
2798 q|β1, q|β0 |πare polynomials in |ε|≤a|β1, |≤a|β2,|4.|4.|4.|4
2804 , |≤a|βs |πwith integer coe∃cients. We shall
2811 interpret the parameters |ε|≤a|β1, |≤a|β2,|4.|4.|4.|4,
2816 |≤a|βs |πas real numbers, and we shall therefore
2824 restrict ourselves to considering the evaluation
2830 of polynomials with real coe∃cients. The |εresult
2837 set R |πof a polynomial chain is de_ned to be
2847 the set of all vectors |ε(q|βn,|4.|4.|4.|4,|4q|β1,|4q|β0)
2853 |πof real numbers which occur as |ε|≤a|β1, |≤a|β2,|4.|4.|4.|
2860 4, |≤a|βs |πindependently assume all possible
2866 real values.|'!|9|4|1|1|1If fbr everyscmoicdsof
2871 |ε∃|4α+↓N41 |πdcszinco inoe∧ers |εj|β0,|4.]4.|4.←4,
2875 j|βt|4|¬A|4|¬T0,|41,|4.|4.|4.|4/|4n|¬Y |πthere
2877 is a nonzero multivariate polynomial |εf |π≤qphhicmz∧brncvb∃
2883 *2cefoyssukv thuw |εf(*2Sβj|mπ,|4.|4.N4.←4,]4q|βj|mt)|4α=↓|40λ
2885 |πfor all |ε(q|βn,N4.|4.|4.←4,|4q|β1,|4q|β0)
2888 |πin |εR, |πlet us say that the result set |εR
2898 |πhas at most |ε+ |πNε-d∧rdessmfffkjedbm,,|[≠kdfhhqwhhhescvq
2902 ucn(6))hqusat mofz |ε+ |πddgrdessofffrdedom.λWe
2906 also say thaz the chain (24),|εcomputes |πa given
2914 polynomial |εu(x)|4α=↓|4uSβnx|gn|4α+↓|4|¬BN44¬O|4←¬B|4α~↓*34=
2915 Sβ1)S4α+↓*44=Sβ0λ|[7kf|ε(u|βn,|4.]4.|4.]4, u|β1/,u|β0)↔|π∪s
2917 in |εR. |πIt follows that a polynomial chain
2925 with at most |ε≡n|π-d∧rjessofffkjedbmmcjknmohcmmvuqzsawl
2929 |εnNπ"hhdd∧rde polyfomiawss(seesexerccues27).←''!|:Y4|1|1|1A
2930 s an examplesof a polynomial chain,,consider
2936 the followingncmwin correspondcng to TheorexnE,
2941 when |εnn|πcs odd:*3'↓A6}|ε&|h|≤lIi26β↓~↓i3Nβi|44∪α≡↓(44*2≤|β1
2943 5i↓~↓Nβ3]βiI4α'↓M44*2≤|β2Nβα"↓Nβ3Nβi!|91|4|¬D|4i|4|¬E|4n/2.|E
2943 |n|;| |≤l|β0|4|Lα=↓|4x>{A2}| |≤l|β1|4|Lα=↓|4|≤a|β1|4α+↓N4|≤l
2945 |β0>{A2}| |≤l|β2|4|Lα=↓|4|≤l|β1|4α⊗↓|4|≤l|β1>
2947 {A2}| |≤l|β3|4|Lα=↓|4|≤a|β2|4α⊗↓|4|≤l|β1>{A2}| |≤l|β1|βα+↓|β
2948 3|βi|4|Lα=↓|4|≤a|β1|βα+↓|β2|βi|4α+↓|4|≤l|β3|βi>
2949 {A2}| |≤l|β2|βα+↓|β3|βi|4|Lα=↓|4|≤a|β2|βα+↓|β2|βi|4α+↓|4|≤l|
2949 β2>{A2}| |ε|≤l|β3|βα~↓⊗|β3←βiI4←Pα*24←≤g|β14β↓∃↓**β3]βi|4α-↓*44
2950 ←≤≤Iβ26βα~↓iβ3|βi>{J6}|π"Theresare |ε*3"⊂n/2]"1|4α∃↓**42λ|π.kq
2952 tippickwivnfsukff|\*2n|[≤jdkppvmf;;|ε|.∩v/66.3P4~↓N41λ|[/vwin
2952 nszeqssafff|εn|4α+↓|41 |πparameter steps),By
2955 Theorem E, the result set |εR |πincludes the
2963 set of all |ε(u|βn,|4.|4.|4.|4, u|β1, u|β0) |πwith
2970 |εu|βnN44=*3↔6α≡↓]41;;|πso (27) computes all polynomials
2975 of degree |εn.λ|πWe cannot prove that |εR |πhassaz
2983 moft |εn |π-d∧gjessofffrdedom,,succdsthescjsuwthssz
2986 huus|ε↔N4~↓*441λ|π/nfdqaffdfo comvonffmy)]''!|9*34|1|1|1|ε%
2988 polynomial chain with s paraxeter szeqs hausaz
2995 mmxyhssde∧rjessofffkjedbm..|[6nnaussffsshhpusiusmb¬vv¬u:?ckk
2995 ," cvmvuqesuufkkcvivnnqqph |εε |[αd∧gjessmfffkjedbmmqqphhpws
2998 sshhqkn|\εh|[↓j∧¬pgjj¬ypqjj¬xezjkf.f}uh dvdn
3000 this intuitive fact is not easy to prove formally;
3009 for example, there are continuous fkkctions (``space-_lling
3016 ckjvjs↔'))qyicm mkqithescjawpppcfsmmmomuuppwkf↔,ukffqqpcvhhh
3017 yjjfxgjsn¬qpuu scngle pjrkmetdr into two independent
3023 parameters. For our purposes↔,we ndedftonvejckxyhhuwhnmmpvgq
3027 fmmcuwpfkkcvpgnfsqqph icme∧∧jccvb∃*2cufmysckknhq¬¬ss{U0}{H10L
folio 614 galley 8
3028 12M29}|πW58320#Computer Programming!ch. 4!f.
3031 614!g. 8C|'{A6}|≡T|≡h|≡e|≡o|≡r|≡e|≡m |≡M (T.
3036 S. Motzkin, 1954).|9|4|εA polynomial chain with
3042 |εm|4|¬Q|40 multiplications has at most 2m degrees
3049 of freedom.|'|'Proof.|9|4|πLet |ε|≤m|β1, |≤m|β2,|4.|4.|4.|4,
3054 |4|≤m|βm |πbe the |ε|≤l|βi'|πs of the chain which
3062 correspond to multiplication operations. Then|'
3067 {A6}|ε|≤m|βi|4|∂α=↓|4S|β2|βi|βα_↓|β1←4α⊗↓|4S|β2|βi,!!1|4|¬E|
3067 4i|4|¬E|4m,|;{A4}| u(x)|4|Lα=↓|4S|β2]βmNβα"↓*4i1,NJ∨(↑↑)2{J6}
3068 Nπwhere each |εS|βj |πis a certain sum of |ε|≤m|π's,
3077 x's, |πand |ε|≤a'|πs. Write |εS|βj|4α=↓|4T|βj|4α+↓|4|≤b|βj,
3082 |πwhere |εT|βjf|π/usuusu¬mmxf|\ε|*2.][(sukff|≥*2)][(sqqppws|\\
3083 ≤XIjk|[7usuusu¬mmxf|≥\*2≤≠][))[]'|::44555557Mgq
3084 I≥k(x) Nπis dxvressible as a polynomial in |εx,
3092 |≤b|β1,|4.|4.|4.|4, |≤b|β2|βm|βα+↓|β1 |πwith
3095 integer coe∃cients. Since the |ε|≤b'|π? are expressible
3102 asslindajnfkkcvpvmfsmxf|\\≤UI17,47[47[47[46,
3103 }≤uIu↔, Nπths set of values represented by all
3111 real values of |ε|≤b|β1,]4.|4.|4.←4,λ|≤b|β2←βm|βα+↓|β1λ|πcon
3114 oainfsthssresuwl ssz offhhsscvquc..HHyjjfxgjshhyjjsujjsiahnm
3116 xyh I≤2m|4α+↓|41 |πdegrees of freedom)?this can
3122 be improved to |{U0}{H10L12M29}|πW58320#Computer
folio 618 galley 9
3126 Programming!ch. 4!f. 618!g. 9C|'{A6}|π!|9|4|1|1|1It
3131 is clear that the results we have obtained about
3140 chains for polynomials in a single variable can
3148 be extended without di∃culty to multivariate
3154 polynomials. For example, if we want to _nd an
3163 optimum scmeme for polynomial evaluation |εwithout
3169 |πadaptation of coe∃cients, we can regard |εu(x)
3176 |πas a polynomial in the |εn|4α+↓|42 |πvjriables
3183 |εx, u|βn,|4.|4.|4.|4, u|β1, u|β0; |πexercise
3188 38 shows that |εn |πmultiplications and |εn |πadditions
3196 are necessary in this case. Indeed, A. Borodcn
3204 [|εTheory of Machines and Computations, |πed.
3210 by Z. Kohavi and A. Paz (]dw York: Academic Press,
3220 1971), 45<58] has proved that Homer's rule (2)
3228 is essentially the |εonly |πway to compute |εu(x)
3236 |πin |ε2n |πoperations without preconditioning.|'
3241 !|9|4|1|1|1With minor variations, the above methods
3247 cjknxbssxxzffddfhomcmaunf invogvcng dcvision,
3250 i.e., to rational functions as well as polynomials.
3258 Curiously, the continued-fraction analog of Homer's
3264 rule now turns out to be optimal from an operation-≡ouft
3274 stafdvocno,nif mkqtiplicjzion andndivision speed
3278 aje equal, even when preconditioning is allowed
3285 (seesexercise 37).]'*1!|9|4|1|1←1*3bmetimes division
3288 is hzlpfkwifkkccgnthesevjluationnoffpogynomcaws,
3290 evdfnthougm pvgyxomcuwqsujdsfd_≡fdfmmvqyicnhzjvxsmxfmkwlpppp
3291 ckwpvmnukffujdkppvm);qwshq¬¬sssefnsx¬¬vpwssmmfhhpisicn
3292 the Shaw<Trakb algorithms for polynomial derivazives.
3298 Akothercsx¬¬vlwsiushhyspvgqxmmvuwp|\*2XVvN4α↓44}}M44}¬M44}¬MI
3298 6α∩I6x|4α"↓|41: |πSince it can be written (|ε)Fgn|gα+↓*3g1|4α
3304 _↓*341)/(xF4↓≠↓|41)↔λ|πwe can evjwuazesip inn
3308 |εllllllllllllllllllllllllllllllllllllllllllllllllllllllllll
3308 lllllllllllllllllllllllll*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!
3308